package 力扣._84_柱状图中的最大矩形;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

class Solution2 {
    public int largestRectangleArea(int[] heights) {
        // 单调栈： 用于找到左/右第一个比当前元素小/大的元素
        // 枚举矩形高度
        //
        // 对于每个元素，找到左/右第一个比起小的元素的位置 O(n)
        // 再遍历一遍，找到最大面积


        int max_s = Integer.MIN_VALUE;  // 最大面积
        int len = heights.length;
        int[] l_index = new int[len];
        int[] r_index = new int[len];
        Arrays.fill(l_index, -1);
        Arrays.fill(r_index, len);

        Deque<Integer> stack = new LinkedList<>();
        // 左边第一个小的
        for (int i = len - 1; i >= 0; i--) {
            if (stack.isEmpty()) {
                stack.push(i);
            } else {
                // 仅让大于栈顶元素的入栈
                while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                    Integer pop = stack.pop();
                    l_index[pop] = i;
                }
                stack.push(i);
            }
        }
        stack.clear();
        // 右边第一个小的
        for (int i = 0; i < len; i++) {
            if (stack.isEmpty()) {
                stack.push(i);
            } else {
                // 仅让大于栈顶元素的入栈
                while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                    Integer pop = stack.pop();
                    r_index[pop] = i;
                }
                stack.push(i);
            }
        }

        for (int i = 0; i < len; i++) {
            max_s = Math.max(max_s, heights[i] * (r_index[i] - l_index[i] - 1));
        }

        return max_s;


    }

    public static void main(String[] args) {
        int i = new Solution2().largestRectangleArea(new int[]{2,1,5,6,2,3});
        System.out.println(i);
    }
}